package leetcode;

import java.util.ArrayList;
import java.util.List;

public class LeetCode143 {

    public static void main(String[] args) {
        ListNode a = new ListNode(1);
        ListNode b = new ListNode(2);
        ListNode c = new ListNode(3);
        ListNode d = new ListNode(4);

        a.next = b;
        b.next = c;
        c.next = d;

        LeetCode143 leetCode143 = new LeetCode143();
        leetCode143.reorderList(a);
        System.out.println(a);
    }

    public void reorderList1(ListNode head) {
        // length-1
        int length = 0;
        ListNode node = head;
        ListNode inverseHead = null;
        while (node != null) {
            ListNode tmpNode = new ListNode(node.val);
            tmpNode.next = inverseHead;
            inverseHead = tmpNode;
            node = node.next;
            length++;
        }
        node = head;
        ListNode inverseNode = inverseHead;
        for (int i = 0; i < length / 2; i++) {
            inverseNode.next = node.next;
            node.next = inverseNode;
            node = node.next;
            inverseNode = inverseNode.next;
        }
        node.next = null;
    }
//------------------------------------------------------------------

    public void reorderList(ListNode head) {
        if (head == null) {
            return;
        }
        //存到 list 中去
        List<ListNode> list = new ArrayList<>();
        while (head != null) {
            list.add(head);
            head = head.next;
        }
        //头尾指针依次取元素
        int i = 0, j = list.size() - 1;
        while (i < j) {
            list.get(i).next = list.get(j);
            i++;
            //偶数个节点的情况，会提前相遇
            if (i == j) {
                break;
            }
            list.get(j).next = list.get(i);
            j--;
        }
        list.get(i).next = null;
    }
}
